package arithmetic1.recall;

/*
    8皇后问题。任意两个皇后不能再同一行，不能再同一列，不能再同一对角线
 */
public class Queen {
    //定义皇后的数量
    private static int max=8;
    //定义一个数组来存储结果
    private static int[] arr=new int[8];
    //计算解的个数
    private static int count=0;

    public static void main(String[] args) {
        //从第一个皇后开始摆
        check(0);
        System.out.printf("共有%d总解",count);
    }

    //摆放皇后
    public static void check(int n){
        if(n==8){   //说明已经把0-7的8个皇后已经摆放好
            print();
            return;
        }else{
            for(int i=0;i<8;i++){
                //将第n个皇后从第0列开始依次摆到第7列
                arr[n]=i;
                if(judge(n)){    //如果这个皇后与之前的皇后不冲突就继续摆放第n+1个皇后
                    check(n+1);
                }
                //如果冲突，就将这个皇后放在下一列
            }
        }
    }

    //判断第n个皇后是否和之前的n-1个皇后冲突
    public static boolean judge(int n){
        for(int i=0;i<n;i++){
            //如果当前皇后和之前的皇后在同一列或者在同一斜线上，就返回false
            if(arr[i]==arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }

    //打印一种摆放的方式
    public static void print(){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        count++;
        System.out.println();
    }
}
